package com.jxb.sort;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 桶排序-将数组中的元素放入桶中，再对每个桶进行排序
 * 1：根据指定容量，元素的数量来创建桶
 * 2：根据元素的大小将数组元素放入对应桶中（通过当前元素的值-最小值）/桶容量
 * 3：对桶中的数据进行排序
 * 4：遍历桶，将数据放入原数组中
 *
 * @author jiaobo
 * @date Created in 2024/12/12 21:21
 **/
public class BucketSort {

    public static void main(String[] args) {
//        int[] nums = {1,4,3,6,0,10,11,9,4,2,6};
//        System.out.println("排序开始----------------->" + Arrays.toString(nums));
//        int[] res = sortArray(nums);
//        System.out.println("排序结束----------------->" + Arrays.toString(res));
        int max = 20;
        int min = 0;
        int bucketCount = (max - min) / 2 + 1;
        System.out.println("桶的数量："+bucketCount);

        int i1 = (3- min)/2;
        System.out.println("元素落在哪个桶"+i1);

        int num = (13%100) / 10;
        System.out.println(num);
    }

    public static int[] sortArray(int[] nums) {
        if(nums.length == 0) {
            return nums;
        }

        //找到桶的最大值和最小值
        int max = 0, min = 0;
        for (int i = 0; i<nums.length; i++) {
            if (nums[i] > max) {
                max = nums[i];
            }
            if (nums[i] < min) {
                min = nums[i];
            }
        }

        //获取桶的数量
        int bucketCount = (max - min) / 2 + 1;

        //构建桶
        List<Integer[]> buckets = new ArrayList<>(bucketCount);
        for (int i = 0; i< bucketCount;i++) {
            buckets.add(new Integer[2]);
        }

        //遍历原数组，填充桶数据
        for (int i = 0; i<nums.length; i++) {
            //根据元素值与最小值的差值/2计算出哪个桶
            int i1 = (nums[i] - min) / 2;
            Integer[] subBucket = buckets.get(i1);
            if (subBucket[0] != null) {
                subBucket[1] = nums[i];
            }else {
                subBucket[0] = nums[i];
            }
        }

        /*看看桶中数据的分布*/
        for (int i = 0; i < buckets.size(); i++) {
            System.out.print("第"+i+"个桶包含数据：");
            System.out.println("桶的分布----------------->" + Arrays.toString(buckets.get(i)));
        }

        //对桶数据进行排序，将先排好序的放入原数组中
        int j = 0;
        for (Integer[] bucket : buckets) {
            //通过选择排序（第二个元素为空，不需要排序）
            xSort(bucket);
            for (int k = 0; k < bucket.length; k++) {
                if (bucket[k] != null) {
                    nums[j] = bucket[k];
                    j++;
                }
            }
        }
        return nums;
    }

    private static void xSort(Integer[] bucket) {
        //当前待排序的内容
        int currentValue;
        for (int i = 0;i<bucket.length-1;i++){
            //已被排序的数据索引
            int preIndex = i;
            //获取当前需要排序的数据
            if (bucket[preIndex + 1]!=null) {
                currentValue = bucket[preIndex + 1];
                while (preIndex >= 0 && currentValue<bucket[preIndex]) {
                    //将已排序的数据向后移动一位
                    bucket[preIndex + 1] = bucket[preIndex];
                    preIndex--;
                }
                //将当前需要排序的数据向前移动一位
                bucket[preIndex + 1] = currentValue;
            }
        }
    }

}
